package fast_fourier_transform;

/**
 * author :  apurv verma
 * email  :  dapurv5@gmail.com
 */



public class FastFourierTransform {
	
	private Complex auxFFT(double A[], Complex w){
		// INVARIANT:Length of A is even at each recursive call
		int len=A.length;
		if (len==1)
			return Complex.toComplex(A[0]);
		double Ae[]=new double[len/2];
		double Ao[]=new double[len/2];
		for(int i=0;i<(len/2);i++){
			Ae[i]=A[2*i];
			Ao[i]=A[2*i+1];
		}
		Complex w2=Complex.multiply(w,w);
		return ( Complex.add(auxFFT(Ae,w2),Complex.multiply(w,auxFFT(Ao,w2))) );
	}
	
	private Complex auxFFT(Complex A[], Complex w){
		// INVARIANT:Length of A is even at each recursive call
		int len=A.length;
		if (len==1)
			return Complex.toComplex(A[0]);
		Complex Ae[]=new Complex[len/2];
		Complex Ao[]=new Complex[len/2];
		for(int i=0;i<(len/2);i++){
			Ae[i]=A[2*i];
			Ao[i]=A[2*i+1];
		}
		Complex w2=Complex.multiply(w,w);
		return ( Complex.add(auxFFT(Ae,w2),Complex.multiply(w,auxFFT(Ao,w2))) );
	}
	
	public Complex[] FFT(double a[]){                 //Returns fourier transform Fa[] of the polynomial a[]
		Complex z=new Complex(1,0);
		int len=a.length;
		double alpha=2*Math.PI/(2*len);
		Complex w=new Complex(Math.cos(alpha),Math.sin(alpha));
		Complex Fa[]=new Complex[2*len];
		
		//Fa[] ACTUALLY REPRESENTS THE VALUE OF THE POLYNOMIAL AT THE (2*len)th ROOTS OF UNITY.
		for(int i=0;i<=2*len-1;i++){
			Fa[i]=auxFFT(a,z);
			z=Complex.multiply(z,w);
		}
		return (Fa);
	}
	
	public double[] invFFT(Complex Fa[]){             //Returns polynomial a[] corresponding to the fourier transform Fa[]
		int len=Fa.length;
		double alpha=2*Math.PI/(len);
		Complex w=new Complex(Math.cos(alpha),Math.sin(alpha));
		Complex inv[]=new Complex[len];
		Complex z=new Complex(1,0);
		for(int i=0;i<len;i++){
			inv[i]=Complex.divide(auxFFT(Fa,Complex.conjugate(z)),len);
			z=Complex.multiply(z,w);
		}
		double a[]=new double[len];
		int k=0;
		for(Complex i: inv){
			if (i.x>0.0001 || i.x<-0.0001){
				a[k]=i.x;
			}
			else
				a[k]=0;
			k++;
		}
		return a;
	}
	
	public Complex[] multiply(Complex c1[], Complex c2[]){
		Complex c[]=new Complex[c1.length];
		for(int i=0;i<c1.length;i++)
			c[i]=Complex.multiply(c1[i], c2[i]);
		return c;
	}
	
}
